package com.leetcode.algorithm.y22.m08.w5;

/**
 * 53. 最大子数组和
 * 
 * https://leetcode.cn/problems/maximum-subarray/
 * 
 * @author jie.deng
 *
 */
class Question0053Solution02 {

	// 贪心算法
	public int maxSubArray(int[] nums) {
		// 前提条件：
		// 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”。
		// 全局最优：选取最大“连续和”
		int len = nums.length;
		int sum = 0;
		int maxSum = Integer.MIN_VALUE;
		for (int i = 0; i < len; i++) {
			if (sum < 0) {
				sum = nums[i];
			} else {
				sum += nums[i];
			}
			maxSum = Math.max(maxSum, sum);
		}
		return maxSum;
	}

}